package wtx.geek;

import java.util.*;
import java.util.Random;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.ForkJoinTask;
import java.util.concurrent.Future;

import com.google.common.base.Joiner;
import javafx.util.Pair;
import sun.plugin.dom.exception.InvalidStateException;

/**
 * Design an algorithm that, given a list of n elements in an array,
 * finds all the elements that appear more than n/3 times in the list.
 * The algorithm should run in linear time ( n >=0 )
 *
 * You are expected to use comparisons and achieve linear time.
 * No hashing/excessive space/ and don't use standard linear time deterministic selection algo

 Link: https://careercup.com/question?id=14099679
 **/

public class Solution {
  /**
   * 采用抵消法，原理就是，大于1/m比例的元素，肯定最多出现m-1个
   * 把这m-1个元素出现的频次和其他元素出现的频次相互抵消，那么
   * 最终剩下的就是这m-1 个元素，我们需要check的就是这m-1个最
   * 多频次出现的元素，count是否大于n/m

   */
  public static int[] findNthElements(int[] array, int m) {
    final int len = array.length;
    int[] eles = new int[m];
    int[] freq = new int[m];
    for (int i = 0; i < m; ++i) {
      freq[i] = 0;
      eles[i] = Integer.MIN_VALUE;
    }
    for (int i = 0; i < len; ++i) {
      boolean matchAny = false;
      for (int j = 0; j < m && !matchAny; ++j) {
        if (eles[j] == array[i]) {
          ++ freq[j];
          matchAny = true;
        } else if (freq[j] <= 0) {
          eles[j] = array[i];
          freq[j] = 1;
          matchAny = true;
        }
      }
      if (!matchAny) {
        for (int j = 0; j < m; ++j) {
          if (--freq[j] <= 0) {
            eles[j] = Integer.MIN_VALUE;
          }
        }
      }
    }
    for (int j = 0; j < m; ++j) {
      freq[j] = 0;
    }
    for (int i = 0; i < len; ++i) {
      for (int j = 0; j < m; ++j) {
        if (eles[j] == array[i]) {
          ++freq[j];
          break;
        }
      }
    }
    int count = len/m;
    int r = 0;
    int[] ret_ele = new int[m];
    for (int i = 0; i < m; ++i) {
      if (freq[i] > count) {
        ret_ele[r++] = eles[i];
      }
    }
    return Arrays.copyOf(ret_ele, r);
  }

  public static void main(String[] args) {
    int[] array = {4, 3, 1, 2, 4, 2, 3, 3, 4, 7};
    int[] freq3 = findNthElements(array, 5);
    StringJoiner sj = new StringJoiner(", ");
    for (int i = 0; i < freq3.length; ++i) {
      sj.add(String.valueOf(freq3[i]));
    }
    System.out.println("n-th elements: " + sj.toString());
  }
}
